LeetCode 136、只出现一次的数字

一、题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例1 :

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

二、题目解析

为了满足 算法应该具有线性时间复杂度与不使用额外空间来实现，本题通过寻找位运算规律来解决。

假设 a = 1, b = 0

1、 1 ⊕ 0 = 1, 0 ⊕ 0 = 0 => a ⊕ 0 = 1, b ⊕ 0 = 0 ==> 任何数与0做异或运算结果均为其本身

2、 1 ⊕ 1 = 0, 0 ⊕ 0 = 0 => a ⊕ a = 0, b ⊕ b = 0 ==> 任何数与其本身做异或运算结果均为0

3、 1 ⊕ 0 ⊕ 1 = 0 => 1 ⊕ 1 = 0 => a ⊕ b ⊕ a = b

​ 1 ⊕ 1 ⊕ 0 = 0 => 0 ⊕ 0 = 0 => a ⊕ a ⊕ b = b

​ 0 ⊕ (1 ⊕ 1) = 0 => 0 ⊕ 0 = 0 => b ⊕ (a ⊕ a) = b

​ ==>异或运算满足交换律和结合律

由于 非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次， 即数组中元素数量恒为奇数。

假设数组中有2n+1个元素，有n个元素为出现两次的元素，如果所有数进行连续异或操作可得：

  A1 ⊕ A1 ⊕ A2 ⊕ A2 ...... ⊕ An ⊕ An ⊕ An+1
= (A1 ⊕ A1) ⊕ (A2 ⊕ A2) ...... ⊕ (An ⊕ An) ⊕ An+1      //通过规律3
= (0) ⊕ (0) ...... ⊕ (0) ⊕ An+1                        //通过规律2
= An+1                                                 //通过规律1

通过规律1可知，我们在做连续异或操作的时候，可以以0为起始数开始运算。

三、参考代码

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

四、复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)